package com.shuo.dsa.niuke;

import com.shuo.dsa.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by shuoGG on 2018/10/21 0021
 */
public class HashSubTree {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) return false;
        String tree = list2Str(preTraversal(root1));
        String subTree = list2Str(preTraversal(root2));
        return tree.contains(subTree);
    }

    private String list2Str(List<Integer> list) {
        StringBuilder ret = new StringBuilder();
        for (Integer integer : list) {
            ret.append(integer).append(".");
        }
        return ret.toString();
    }

    private List<Integer> preTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.value);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        return ret;
    }

    private void preTraversalCur(TreeNode root) {
        if (root == null)
            return;
        System.out.println(root.value);
        preTraversalCur(root.left);
        preTraversalCur(root.right);
    }
}
